<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>9大排序算法 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/64.6f8bb1fa.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/55.d8f9004b.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/60.ab782775.js"><link rel="prefetch" href="/assets/js/61.6dd12daf.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/63.6f8a4742.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/66.360c2d2b.js"><link rel="prefetch" href="/assets/js/67.26f84d32.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/9.3813842d.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>9大排序算法</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_01-算法的记忆『9-2』" class="sidebar-link">01.算法的记忆『9+2』</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-1-时间复杂度『记』" class="sidebar-link">1.1.时间复杂度『记』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-2-空间复杂度『记』" class="sidebar-link">1.2.空间复杂度『记』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-3-算法稳定性『记』" class="sidebar-link">1.3.算法稳定性『记』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-4-其他小提示『记』" class="sidebar-link">1.4.其他小提示『记』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-5-外部排序" class="sidebar-link">1.5.外部排序</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_02-排序『数组』模板⭐️" class="sidebar-link">02.排序『数组』模板⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-0-排序数组版『面试代码框架』" class="sidebar-link">2.0.排序数组版『面试代码框架』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-1-选择排序（selectsort）" class="sidebar-link">2.1.选择排序（SelectSort）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-2-冒泡排序（bubblesort）" class="sidebar-link">2.2.冒泡排序（BubbleSort）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-3-插入排序（insertsort）" class="sidebar-link">2.3.插入排序（InsertSort）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-4-希尔排序（shell-sort）" class="sidebar-link">2.4.希尔排序（Shell Sort）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-5-堆排序（heapsort）" class="sidebar-link">2.5.堆排序（HeapSort）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#✅『需要2个函数的排序』" class="sidebar-link">✅『需要2个函数的排序』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-6-归并排序" class="sidebar-link">2.6.归并排序</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-7-快速排序" class="sidebar-link">2.7.快速排序</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_03-排序『链表』模板⭐️" class="sidebar-link">03.排序『链表』模板⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_3-1-选择排序" class="sidebar-link">3.1.选择排序</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_3-3-插入排序" class="sidebar-link">3.3.插入排序</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#✅『2大』" class="sidebar-link">✅『2大』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_3-6-归并排序" class="sidebar-link">3.6.归并排序</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_3-7-快速排序" class="sidebar-link">3.7.快速排序</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_04-三种线性排序" class="sidebar-link">04.三种线性排序</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#✅前述" class="sidebar-link">✅前述</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#✅计数排序（counting-sort）读音是第4声" class="sidebar-link">✅计数排序（counting sort）读音是第4声</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-假设和操作" class="sidebar-link">1.假设和操作</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-算法分析" class="sidebar-link">2.算法分析</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_3-局限性" class="sidebar-link">3.局限性</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#✅基数排序（radix-sort）读音是第1声" class="sidebar-link">✅基数排序（Radix sort）读音是第1声</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-操作" class="sidebar-link">1.操作</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-疑问" class="sidebar-link">2.疑问</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_3-算法分析" class="sidebar-link">3.算法分析</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#✅桶排序（bucket-sort）" class="sidebar-link">✅桶排序（bucket sort）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_1-假设和操作：" class="sidebar-link">1.假设和操作：</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_2-算法分析-2" class="sidebar-link">2.算法分析</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#✅联系和总结" class="sidebar-link">✅联系和总结</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_05-查找类算法" class="sidebar-link">05.查找类算法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_5-1-二分查找" class="sidebar-link">5.1.二分查找</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#_5-2-其他查找算法" class="sidebar-link">5.2.其他查找算法</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part01.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF.html#参考资料" class="sidebar-link">参考资料</a><ul class="sidebar-sub-headers"></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="_9大排序算法"><a href="#_9大排序算法" class="header-anchor">#</a> 9大排序算法</h1> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>&lt;font style=&quot;background:yellow&quot;&gt;
排序算法复杂度记忆、排序模板、二分查找模板
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h2 id="_01-算法的记忆『9-2』"><a href="#_01-算法的记忆『9-2』" class="header-anchor">#</a> 01.算法的记忆『9+2』</h2> <div class="language-html line-numbers-mode"><pre class="language-html"><code><span class="token tag"><span class="token tag"><span class="token punctuation">&lt;</span>details</span><span class="token punctuation">&gt;</span></span>
<span class="token tag"><span class="token tag"><span class="token punctuation">&lt;</span>summary</span><span class="token punctuation">&gt;</span></span>学习排序算法的『原因』<span class="token tag"><span class="token tag"><span class="token punctuation">&lt;/</span>summary</span><span class="token punctuation">&gt;</span></span> 
<span class="token tag"><span class="token tag"><span class="token punctuation">&lt;</span>pre</span><span class="token punctuation">&gt;</span></span><span class="token tag"><span class="token tag"><span class="token punctuation">&lt;</span>code</span><span class="token punctuation">&gt;</span></span>
获取排序算法中的『思想』
<span class="token tag"><span class="token tag"><span class="token punctuation">&lt;/</span>code</span><span class="token punctuation">&gt;</span></span><span class="token tag"><span class="token tag"><span class="token punctuation">&lt;/</span>pre</span><span class="token punctuation">&gt;</span></span>
<span class="token tag"><span class="token tag"><span class="token punctuation">&lt;/</span>details</span><span class="token punctuation">&gt;</span></span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><p><strong>『1』插入类排序（3种）</strong></p> <ul><li><p>直接插入排序</p></li> <li><p>折半插入排序</p></li> <li><p>希尔排序</p></li></ul> <p><strong>『2』选择类排序（2种）</strong></p> <ul><li><p>简单选择排序</p></li> <li><p>堆排序</p> <ul><li>重点在于训练“堆”这种数据结构</li></ul></li></ul> <p><strong>『3』 交换类排序（2种）</strong></p> <ul><li><p>冒泡排序</p></li> <li><p>快速排序</p> <ul><li>训练“双指针”技巧、分治算法</li></ul></li></ul> <p><strong>『4』归并类（1种）</strong></p> <ul><li><p>二路归并排序</p> <ul><li>训练用空间换时间的思维、while循环的写法强化</li></ul></li></ul> <p><strong>『5』 『不基于比较』的排序算法类（1种）</strong></p> <ul><li>基数排序</li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>以上为考研中的9大排序算法。
就业面试中，不基于比较的排序算法类（3种）
- 基数排序

- 计数排序
- 桶排序
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><blockquote><p>记忆：</p></blockquote> <ul><li>5大类排序算法，对应3+2+2+1+1</li> <li>9大考研基础排序算法+2大就业排序算法</li></ul> <h3 id="_1-1-时间复杂度『记』"><a href="#_1-1-时间复杂度『记』" class="header-anchor">#</a> 1.1.时间复杂度『记』</h3> <h4 id="（1）平均时间复杂度："><a href="#（1）平均时间复杂度：" class="header-anchor">#</a> （1）<font style="background:yellow;"><strong>平均</strong></font>时间复杂度：</h4> <ul><li>1、军训的时候，教官说：<strong>快些</strong>以『O(<strong>nlogn</strong>)』的速度<strong>归队</strong>
（快速排序、希尔排序、归并排序、堆排序）</li> <li>2、特殊的比如：基数排序，平均时间复杂度『O(d(n+r))』</li> <li>3、9大排序中，<strong>others其他</strong>的没有列入的都是『<strong>O(n<sup>2</sup>)</strong>』</li></ul> <h4 id="（2）最坏时间复杂度"><a href="#（2）最坏时间复杂度" class="header-anchor">#</a> （2）<font style="background:yellow;">最<strong>坏</strong></font>时间复杂度</h4> <ul><li>9大排序中，除了<strong>快速排序</strong>是『<strong>O(n<sup>2</sup>)</strong>』之外，其他的和<strong>平均时间复杂度</strong>一致</li></ul> <h4 id="（3）最好时间复杂度如下："><a href="#（3）最好时间复杂度如下：" class="header-anchor">#</a> （3）<font style="background:yellow;"><strong>最好</strong></font>时间复杂度如下：</h4> <ul><li>我觉得，冒泡之所以是n，或许是改进的版本，不然根本不能。</li></ul> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%9C%80%E5%A5%BD%E6%9C%80%E5%9D%8F.png" alt="排序算法最好最坏"></p> <h3 id="_1-2-空间复杂度『记』"><a href="#_1-2-空间复杂度『记』" class="header-anchor">#</a> 1.2.空间复杂度『记』</h3> <p>1、特殊的：</p> <ul><li><p><strong>快速</strong>排序为<font style="background:yellow;">『<strong>O(logn)</strong>』</font>——天勤上是『O(log<sub>2</sub>n)』</p></li> <li><p><strong>归并</strong>排序为<font style="background:yellow;">『<strong>O(n)</strong>』</font></p></li> <li><p>基数排序为『<strong>O(n+m)</strong>』</p> <p>2、9大排序中others（其他）的，都是『O(1)』</p></li></ul> <h3 id="_1-3-算法稳定性『记』"><a href="#_1-3-算法稳定性『记』" class="header-anchor">#</a> 1.3.算法稳定性『记』</h3> <p>复习痛苦，情绪<strong>不稳定</strong>，<strong>快些选堆</strong>好友来聊天。<br>
（快速排序、希尔排序、<strong>简单选择</strong>排序、堆排序）</p> <p>其他的是稳定的。</p> <p>注意点：关于“简单选择排序”<br>
数组中的“交换版本”的为不稳定版本。<br>
链表中的“插入版本”的为稳定版本。</p> <ul><li>说到底就是，稳定不稳定，我们还是要看实现，但是如果没有具体说明算法执行流程，我们大致说：不稳定。</li></ul> <h3 id="_1-4-其他小提示『记』"><a href="#_1-4-其他小提示『记』" class="header-anchor">#</a> 1.4.其他小提示『记』</h3> <ul><li>1、基于“比较”的排序，在<strong>最坏</strong>的情况下的<strong>时间</strong>复杂度至少是  『O(nlogn)』</li> <li>我以前还纠结到底是『O(nlogn)』还是『O(logn)』来着，后面大致给自己想了一个理解方式：</li> <li>『O(logn)』比『O(n)』增长慢，但是“基数排序”这样的不基于比较的算法才线性，那么我们基于比较的应该比他慢一些，时间要长一点。</li> <li>2、『『希尔排序时间复杂度很奇特。。。。。』</li></ul> <blockquote><p>2020版<a href="https://book.douban.com/subject/30777887/" target="_blank" rel="noopener noreferrer">数据结构高分笔记<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>（第8版），率辉</p></blockquote> <h3 id="_1-5-外部排序"><a href="#_1-5-外部排序" class="header-anchor">#</a> 1.5.外部排序</h3> <h2 id="_02-排序『数组』模板⭐️"><a href="#_02-排序『数组』模板⭐️" class="header-anchor">#</a> 02.排序『数组』模板⭐️</h2> <ul><li>Author：HACV</li> <li>Review：HACV、xeknrc</li></ul> <h3 id="_2-0-排序数组版『面试代码框架』"><a href="#_2-0-排序数组版『面试代码框架』" class="header-anchor">#</a> 2.0.排序数组版『面试代码框架』</h3> <ul><li>一定要记住三个函数！</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code> <span class="token comment">//1、播种随机数种子，如果不播种，也行，只是每次运行随机都是一样的。 </span>
 <span class="token function">srand</span><span class="token punctuation">(</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
 <span class="token function">random_shuffle</span><span class="token punctuation">(</span> arr<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">,</span> arr<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//arr是vector,2、面试用来生成随机数字序列 </span>
 <span class="token function">reverse</span><span class="token punctuation">(</span> arr<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> arr<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//arr是vector</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><ul><li>模板开始</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token comment">//设置全局函数方便自己</span>
vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> arr<span class="token punctuation">;</span>
<span class="token keyword">int</span> len<span class="token punctuation">;</span>


<span class="token comment">//——————————————————————某某排序模板放置位置——————————————————————</span>
<span class="token comment">//选择排序</span>
<span class="token comment">//void SelectSort(vector&lt;int&gt; &amp;solve)</span>
<span class="token keyword">void</span> <span class="token function">SelectSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span><span class="token punctuation">(</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> preMin<span class="token operator">=</span>i<span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span> j<span class="token operator">&lt;</span>len<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&lt;</span> arr<span class="token punctuation">[</span>preMin<span class="token punctuation">]</span> <span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				preMin<span class="token operator">=</span>j<span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>

		<span class="token function">swap</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>preMin<span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//调用函数，简化代码，也提高代码可读性</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>



<span class="token comment">//———————————————————————————————排序模板『vector数组版』——————————————————————————</span>
<span class="token keyword">void</span> <span class="token function">HelpSort</span><span class="token punctuation">(</span> <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//选择自己写的排序函数，比如我们选择『选择排序』</span>
	<span class="token function">SelectSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//模板：函数名称</span>
    
    <span class="token comment">//『如果面试官，看你现在写的是从大到小或者从小到大，让你改一下排序方向</span>
    <span class="token comment">//那你就加上下面一行，来讲已经排序好的反转一下『后续的排序代码中，只管自己怎么高兴怎么写</span>
    <span class="token comment">//不考虑从大到小，还是从小到大『尽量从小到大』</span>
    <span class="token function">reverse</span><span class="token punctuation">(</span> arr<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> arr<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//1、播种随机数种子，如果不播种，也行，只是每次运行随机都是一样的。 </span>
	<span class="token function">srand</span><span class="token punctuation">(</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

	<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>len <span class="token punctuation">)</span><span class="token punctuation">;</span>
	arr<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span> len <span class="token punctuation">)</span><span class="token punctuation">;</span>	

	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>i<span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token comment">//2、面试用来生成随机数字序列 </span>
	<span class="token function">random_shuffle</span><span class="token punctuation">(</span> arr<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">,</span> arr<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

	<span class="token function">HelpSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//辅助排序函数</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d &quot;</span><span class="token punctuation">,</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">//———————————————————————————————排序模板『vector数组版』——————————————————————————</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br></div></div><h3 id="_2-1-选择排序（selectsort）"><a href="#_2-1-选择排序（selectsort）" class="header-anchor">#</a> 2.1.选择排序（SelectSort）</h3> <ul><li>从小到大</li> <li>牛客网-<a href="https://www.nowcoder.com/questionTerminal/5048367d2e934a14a933c9c5ba398632" target="_blank" rel="noopener noreferrer">选择排序<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//设置全局函数方便自己</span>
vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> arr<span class="token punctuation">;</span>
<span class="token keyword">int</span> len<span class="token punctuation">;</span>

<span class="token comment">//选择排序</span>
<span class="token keyword">void</span> <span class="token function">SelectSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span><span class="token punctuation">(</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> CurMin<span class="token operator">=</span>i<span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span> j<span class="token operator">&lt;</span>len<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&lt;</span> arr<span class="token punctuation">[</span>CurMin<span class="token punctuation">]</span> <span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				CurMin<span class="token operator">=</span>j<span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>

		<span class="token function">swap</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>CurMin<span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>


</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br></div></div><h3 id="_2-2-冒泡排序（bubblesort）"><a href="#_2-2-冒泡排序（bubblesort）" class="header-anchor">#</a> 2.2.冒泡排序（BubbleSort）</h3> <ul><li><p>从小到大</p></li> <li><p>编程技巧：『逆向思维，倒着遍历』</p></li></ul> <h4 id="_2-2-1-未优化版"><a href="#_2-2-1-未优化版" class="header-anchor">#</a> 2.2.1.未优化版</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//冒泡排序——我们用『逆向思维，倒着遍历』</span>
<span class="token keyword">void</span> <span class="token function">BubbleSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//逆向思维loop，倒着遍历</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> loop<span class="token operator">=</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> loop<span class="token operator">&gt;</span><span class="token number">0</span><span class="token punctuation">;</span> <span class="token operator">--</span>loop<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;</span>loop<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&gt;</span>arr<span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">)</span> 
			<span class="token punctuation">{</span>
				<span class="token function">swap</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><h4 id="_2-2-2-优化版"><a href="#_2-2-2-优化版" class="header-anchor">#</a> 2.2.2.优化版</h4> <ul><li>增加一个辅助变量『空间换时间』</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//冒泡排序——我们用『逆向思维，倒着遍历』</span>
<span class="token keyword">void</span> <span class="token function">BubbleSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//逆向思维</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> loop<span class="token operator">=</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> loop<span class="token operator">&gt;</span><span class="token number">0</span><span class="token punctuation">;</span> <span class="token operator">--</span>loop<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token comment">//辅助变量</span>
		<span class="token keyword">bool</span> tag<span class="token operator">=</span><span class="token boolean">true</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;</span>loop<span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&gt;</span>arr<span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">)</span> 
			<span class="token punctuation">{</span>
				<span class="token function">swap</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
				<span class="token comment">//如果有调换位置，说明无序</span>
				tag<span class="token operator">=</span><span class="token boolean">false</span><span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>

		<span class="token comment">//辅助变量没有变化，那肯定有序了，管你多少循环，我才懒得继续了</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span> tag <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">break</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br></div></div><h3 id="_2-3-插入排序（insertsort）"><a href="#_2-3-插入排序（insertsort）" class="header-anchor">#</a> 2.3.插入排序（InsertSort）</h3> <ul><li><p>从小到大</p></li> <li><p>编码技巧：『逆向思维，倒着遍历』</p></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">InsertSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//第1个元素，局部有序，所以我们从第2个元素，也就是1号开始</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> loop<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> loop<span class="token operator">&lt;</span>len<span class="token punctuation">;</span> <span class="token operator">++</span>loop<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
        <span class="token comment">//『坑点』：记得，一定要弄好下标</span>
		<span class="token keyword">int</span> CurNum<span class="token operator">=</span>loop<span class="token punctuation">;</span>
        
		<span class="token comment">//逆向思维</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> inner<span class="token operator">=</span>loop<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> inner<span class="token operator">&gt;=</span><span class="token number">0</span><span class="token punctuation">;</span> <span class="token operator">--</span>inner<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>CurNum<span class="token punctuation">]</span><span class="token operator">&lt;</span>arr<span class="token punctuation">[</span>inner<span class="token punctuation">]</span> <span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				<span class="token function">swap</span><span class="token punctuation">(</span> arr<span class="token punctuation">[</span>CurNum<span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>inner<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
                 <span class="token comment">//『坑点』记得更新下标</span>
				CurNum<span class="token operator">=</span>inner<span class="token punctuation">;</span>
			<span class="token punctuation">}</span> 
			<span class="token keyword">else</span>
			<span class="token punctuation">{</span>
				<span class="token keyword">break</span><span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span><span class="token comment">//end for内部循环</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br></div></div><ul><li>写法2，参见CyC2018『上述应该已经够清晰了』</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">InsertSort</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token operator">&amp;</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> len<span class="token punctuation">)</span>
<span class="token punctuation">{</span>  
   <span class="token comment">//因为第0号元素默认有序，所以从i=1开始</span>
   <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
   <span class="token punctuation">{</span>
       <span class="token comment">//待插入元素</span>
       <span class="token keyword">int</span> num<span class="token operator">=</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
       
       <span class="token comment">//从后往前面扫描</span>
       <span class="token keyword">int</span> loop<span class="token operator">=</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
       <span class="token keyword">while</span><span class="token punctuation">(</span> loop<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> num<span class="token operator">&lt;</span>arr<span class="token punctuation">[</span>loop<span class="token punctuation">]</span> <span class="token punctuation">)</span>
       <span class="token punctuation">{</span>
           <span class="token comment">//右移</span>
           arr<span class="token punctuation">[</span>loop<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>loop<span class="token punctuation">]</span><span class="token punctuation">;</span>
           <span class="token operator">--</span>loop<span class="token punctuation">;</span>
       <span class="token punctuation">}</span>

       arr<span class="token punctuation">[</span>loop<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>num<span class="token punctuation">;</span>
   <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br></div></div><h3 id="_2-4-希尔排序（shell-sort）"><a href="#_2-4-希尔排序（shell-sort）" class="header-anchor">#</a> 2.4.希尔排序（Shell Sort）</h3> <ul><li>从小到大</li> <li>希尔排序，其实是对『插入排序』的改进</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">ShellSort</span><span class="token punctuation">(</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span>  <span class="token operator">&amp;</span> solve <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> Len<span class="token operator">=</span>solve<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token comment">//获得希尔排序的增量，最接近Len的一个。。</span>
	<span class="token keyword">int</span> h<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> h<span class="token operator">&lt;</span> Len<span class="token operator">/</span><span class="token number">3</span> <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		h<span class="token operator">=</span><span class="token number">3</span><span class="token operator">*</span>h<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	<span class="token keyword">while</span> <span class="token punctuation">(</span>h <span class="token operator">&gt;=</span> <span class="token number">1</span><span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> h<span class="token punctuation">;</span> i <span class="token operator">&lt;</span> Len<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> 
		<span class="token punctuation">{</span>
            <span class="token comment">//从后往前遍历『j&gt;=h &amp;&amp; solve[j]&lt;solve[j-h]』</span>
			<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i<span class="token punctuation">;</span> j <span class="token operator">&gt;=</span> h <span class="token operator">&amp;&amp;</span> solve<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&lt;</span>solve<span class="token punctuation">[</span>j<span class="token operator">-</span>h<span class="token punctuation">]</span> <span class="token punctuation">;</span> j <span class="token operator">-=</span> h<span class="token punctuation">)</span> 
			<span class="token punctuation">{</span>
				<span class="token function">swap</span><span class="token punctuation">(</span> solve<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> solve<span class="token punctuation">[</span>j<span class="token operator">-</span>h<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>
        
        <span class="token comment">//逐步缩小增量的大小</span>
		h <span class="token operator">=</span> h <span class="token operator">/</span> <span class="token number">3</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br></div></div><ul><li>参考自：CyC2018</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">shellSort</span><span class="token punctuation">(</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token operator">&amp;</span> arr <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//希尔排序的增量</span>
	<span class="token keyword">int</span> d<span class="token operator">=</span>arr<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> d<span class="token operator">&gt;</span><span class="token number">1</span> <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token comment">//使用希尔增量的方式，即每次折半</span>
		d<span class="token operator">=</span>d<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> loop<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> loop<span class="token operator">&lt;</span>d<span class="token punctuation">;</span> <span class="token operator">++</span>loop<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>loop<span class="token operator">+</span>d<span class="token punctuation">;</span> i<span class="token operator">&lt;</span>arr<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">+=</span>d <span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				<span class="token keyword">int</span> temp<span class="token operator">=</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
				<span class="token keyword">int</span> j<span class="token punctuation">;</span>
				<span class="token keyword">for</span><span class="token punctuation">(</span> j<span class="token operator">=</span>i<span class="token operator">-</span>d<span class="token punctuation">;</span> j<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&gt;</span>temp<span class="token punctuation">;</span> j<span class="token operator">=</span>j<span class="token operator">-</span>d <span class="token punctuation">)</span>
				<span class="token punctuation">{</span>
					arr<span class="token punctuation">[</span>j<span class="token operator">+</span>d<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
				<span class="token punctuation">}</span>
				arr<span class="token punctuation">[</span>j<span class="token operator">+</span>d<span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>	
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br></div></div><ul><li>参考自：<a href="http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653199674&idx=1&sn=9ab7bb7e465104c67a3d8590ebd0fe6c&chksm=8c99efe0bbee66f69c07e5f423d7751c9667fa82beb6dcaef4c0e96dac9545d2277c8179c765&mpshare=1&scene=23&srcid=07308vsccvQJK6IkPsvCOwrJ&sharer_sharetime=1627647161435&sharer_shareid=7d02bdfe8ee477ab2b773f2df63f3163#rd" target="_blank" rel="noopener noreferrer">程序员小灰<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h3 id="_2-5-堆排序（heapsort）"><a href="#_2-5-堆排序（heapsort）" class="header-anchor">#</a> 2.5.堆排序（HeapSort）</h3> <blockquote><p>从小到大</p> <p>思想：局部治理，问题一步步变小，减而治之</p></blockquote> <ul><li>参考题目：<a href="https://www.nowcoder.com/questionTerminal/ed8308a5f0f744fc936bdba78c15f810?f=discussion" target="_blank" rel="noopener noreferrer">排序（堆排序）<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> solve<span class="token punctuation">;</span>
<span class="token comment">//辅助函数1</span>
<span class="token keyword">void</span> <span class="token function">up2downSink</span><span class="token punctuation">(</span><span class="token keyword">int</span> upPos<span class="token punctuation">,</span> <span class="token keyword">int</span> downPos<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> needModify<span class="token operator">=</span>upPos<span class="token punctuation">;</span>
	<span class="token keyword">int</span> LChild<span class="token operator">=</span>needModify<span class="token operator">*</span><span class="token number">2</span><span class="token punctuation">;</span>

	<span class="token keyword">while</span><span class="token punctuation">(</span> LChild<span class="token operator">&lt;=</span>downPos <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> RChild<span class="token operator">=</span>LChild<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span> RChild<span class="token operator">&lt;=</span>downPos <span class="token operator">&amp;&amp;</span> solve<span class="token punctuation">[</span>RChild<span class="token punctuation">]</span><span class="token operator">&gt;</span>solve<span class="token punctuation">[</span>LChild<span class="token punctuation">]</span> <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			LChild<span class="token operator">=</span>RChild<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>

		<span class="token keyword">if</span><span class="token punctuation">(</span> solve<span class="token punctuation">[</span>LChild<span class="token punctuation">]</span><span class="token operator">&gt;</span>solve<span class="token punctuation">[</span>needModify<span class="token punctuation">]</span> <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token function">swap</span><span class="token punctuation">(</span> solve<span class="token punctuation">[</span>LChild<span class="token punctuation">]</span><span class="token punctuation">,</span> solve<span class="token punctuation">[</span>needModify<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
			needModify<span class="token operator">=</span>LChild<span class="token punctuation">;</span>
			LChild<span class="token operator">=</span>needModify<span class="token operator">*</span><span class="token number">2</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		<span class="token keyword">else</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">break</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>



<span class="token comment">//辅助函数2</span>
<span class="token comment">//创建大顶堆【begin,end】</span>
<span class="token keyword">void</span> <span class="token function">createMaxHeap</span><span class="token punctuation">(</span><span class="token keyword">int</span> begin<span class="token punctuation">,</span> <span class="token keyword">int</span> end <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> loop<span class="token operator">=</span><span class="token punctuation">(</span>end<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span> loop<span class="token operator">&gt;=</span>begin<span class="token punctuation">;</span> <span class="token operator">--</span>loop <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">up2downSink</span><span class="token punctuation">(</span>loop<span class="token punctuation">,</span> end<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>


<span class="token comment">//核心代码【begin,end】</span>
<span class="token keyword">void</span> <span class="token function">heapSort</span><span class="token punctuation">(</span><span class="token keyword">int</span> begin<span class="token punctuation">,</span> <span class="token keyword">int</span> end<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> begin<span class="token operator">&gt;=</span>end <span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">;</span>
	
	<span class="token function">createMaxHeap</span><span class="token punctuation">(</span> begin<span class="token punctuation">,</span> end <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> loop<span class="token operator">=</span>end<span class="token punctuation">;</span> loop<span class="token operator">&gt;</span>begin<span class="token punctuation">;</span> <span class="token operator">--</span>loop<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token comment">//将大顶堆的最大值solve[begin]和当前最后的元素换位置</span>
		<span class="token function">swap</span><span class="token punctuation">(</span> solve<span class="token punctuation">[</span>loop<span class="token punctuation">]</span><span class="token punctuation">,</span> solve<span class="token punctuation">[</span>begin<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token comment">//将插入的元素，进行下沉，到我们不能管的边界loop-1</span>
		<span class="token comment">//因为我们认为，loop已经可以了</span>
		<span class="token function">up2downSink</span><span class="token punctuation">(</span>begin<span class="token punctuation">,</span> loop<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> n<span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span> <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		solve<span class="token punctuation">.</span><span class="token function">resize</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>solve<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		<span class="token function">heapSort</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d%c&quot;</span><span class="token punctuation">,</span>solve<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> i<span class="token operator">!=</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token string">' '</span> <span class="token operator">:</span> <span class="token string">'\n'</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>


	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br></div></div><h3 id="✅『需要2个函数的排序』"><a href="#✅『需要2个函数的排序』" class="header-anchor">#</a> ✅『需要2个函数的排序』</h3> <h3 id="_2-6-归并排序"><a href="#_2-6-归并排序" class="header-anchor">#</a> 2.6.归并排序</h3> <h5 id="_2-6-1-一般版本"><a href="#_2-6-1-一般版本" class="header-anchor">#</a> 2.6.1.一般版本</h5> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//归并排序</span>
<span class="token comment">//1.子函数——归并</span>

<span class="token keyword">void</span> <span class="token function">merge</span><span class="token punctuation">(</span> <span class="token keyword">int</span> Left<span class="token punctuation">,</span> <span class="token keyword">int</span> mid<span class="token punctuation">,</span> <span class="token keyword">int</span> Right <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> Len<span class="token operator">=</span>Right<span class="token operator">-</span>Left<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
	vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">Help</span><span class="token punctuation">(</span> Len <span class="token punctuation">)</span><span class="token punctuation">;</span>


	<span class="token keyword">int</span> ii<span class="token operator">=</span>Left<span class="token punctuation">;</span>
	<span class="token keyword">int</span> jj<span class="token operator">=</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> pre<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> ii<span class="token operator">&lt;=</span>mid <span class="token operator">&amp;&amp;</span> jj<span class="token operator">&lt;=</span>Right <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		Help<span class="token punctuation">[</span>pre<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span> <span class="token punctuation">(</span> arr<span class="token punctuation">[</span>ii<span class="token punctuation">]</span><span class="token operator">&lt;</span>arr<span class="token punctuation">[</span>jj<span class="token punctuation">]</span><span class="token operator">?</span> arr<span class="token punctuation">[</span>ii<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">:</span> arr<span class="token punctuation">[</span>jj<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>


	<span class="token keyword">while</span><span class="token punctuation">(</span> ii<span class="token operator">&lt;=</span>mid <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		Help<span class="token punctuation">[</span>pre<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>ii<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>


	<span class="token keyword">while</span><span class="token punctuation">(</span> jj<span class="token operator">&lt;=</span>Right <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		Help<span class="token punctuation">[</span>pre<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>jj<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span> 
    
	<span class="token comment">//记得，拷贝回去，注意是把Help辅助数组中的数字复制回去</span>
	<span class="token function">copy</span><span class="token punctuation">(</span> Help<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> Help<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> arr<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">+</span>Left <span class="token punctuation">)</span><span class="token punctuation">;</span>
	
<span class="token punctuation">}</span>


<span class="token comment">//2.子函数——递归分治，划分</span>
<span class="token keyword">void</span> <span class="token function">MergeSort</span><span class="token punctuation">(</span> <span class="token keyword">int</span> Left<span class="token punctuation">,</span> <span class="token keyword">int</span> Right <span class="token punctuation">)</span>
<span class="token punctuation">{</span>

	<span class="token keyword">if</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token comment">//int mid=(Left+Right)/2;这样写，容易溢出</span>
         <span class="token keyword">int</span> mid<span class="token operator">=</span> Right<span class="token operator">+</span> <span class="token punctuation">(</span>Left<span class="token operator">-</span>Right<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span> <span class="token comment">//这样就防止溢出了</span>
		<span class="token function">MergeSort</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> mid <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">MergeSort</span><span class="token punctuation">(</span> mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>	<span class="token comment">//注意，是mid+1</span>
		<span class="token function">merge</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> mid <span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br></div></div><h5 id="_2-6-2-合并上面操作的代码"><a href="#_2-6-2-合并上面操作的代码" class="header-anchor">#</a> 2.6.2.合并上面操作的代码</h5> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">MergeSort</span><span class="token punctuation">(</span> <span class="token keyword">int</span> Left<span class="token punctuation">,</span> <span class="token keyword">int</span> Right <span class="token punctuation">)</span>
<span class="token punctuation">{</span>

	<span class="token keyword">if</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> mid<span class="token operator">=</span><span class="token punctuation">(</span>Left<span class="token operator">+</span>Right<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
		<span class="token function">MergeSort</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> mid <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">MergeSort</span><span class="token punctuation">(</span> mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>
        
        <span class="token comment">//其实下面，就是将合并函数粘贴了过来</span>
		<span class="token keyword">int</span> Len<span class="token operator">=</span>Right<span class="token operator">-</span>Left<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
		vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">Help</span><span class="token punctuation">(</span> Len <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> ii<span class="token operator">=</span>Left<span class="token punctuation">;</span>
		<span class="token keyword">int</span> jj<span class="token operator">=</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> pre<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
		<span class="token keyword">while</span><span class="token punctuation">(</span> ii<span class="token operator">&lt;=</span>mid <span class="token operator">&amp;&amp;</span> jj<span class="token operator">&lt;=</span>Right <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			Help<span class="token punctuation">[</span>pre<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span> <span class="token punctuation">(</span> arr<span class="token punctuation">[</span>ii<span class="token punctuation">]</span><span class="token operator">&lt;</span>arr<span class="token punctuation">[</span>jj<span class="token punctuation">]</span><span class="token operator">?</span> arr<span class="token punctuation">[</span>ii<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">:</span> arr<span class="token punctuation">[</span>jj<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>


		<span class="token keyword">while</span><span class="token punctuation">(</span> ii<span class="token operator">&lt;=</span>mid <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			Help<span class="token punctuation">[</span>pre<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>ii<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>


		<span class="token keyword">while</span><span class="token punctuation">(</span> jj<span class="token operator">&lt;=</span>Right <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			Help<span class="token punctuation">[</span>pre<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>jj<span class="token operator">++</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span> 

		<span class="token function">copy</span><span class="token punctuation">(</span> Help<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> Help<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> arr<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">+</span>Left <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br></div></div><h5 id="_2-6-3-从大到小"><a href="#_2-6-3-从大到小" class="header-anchor">#</a> 2.6.3.从大到小</h5> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">Merge</span><span class="token punctuation">(</span><span class="token keyword">int</span> Left<span class="token punctuation">,</span> <span class="token keyword">int</span> mid<span class="token punctuation">,</span> <span class="token keyword">int</span> Right<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> Len<span class="token operator">=</span>Right<span class="token operator">-</span>Left<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> LenOne<span class="token operator">=</span>mid<span class="token punctuation">;</span>	<span class="token comment">//『从大到小』</span>
	<span class="token keyword">int</span> LenTwo<span class="token operator">=</span>Right<span class="token punctuation">;</span>
	vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">Help</span><span class="token punctuation">(</span>Len<span class="token punctuation">)</span><span class="token punctuation">;</span>


	<span class="token keyword">int</span> CurNum<span class="token operator">=</span>Len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token comment">//注意是LenOne到Left，而不是到0</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> LenOne<span class="token operator">&gt;=</span>Left <span class="token operator">&amp;&amp;</span> LenTwo<span class="token operator">&gt;</span>mid <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span> solve<span class="token punctuation">[</span>LenOne<span class="token punctuation">]</span><span class="token operator">&gt;</span>solve<span class="token punctuation">[</span>LenTwo<span class="token punctuation">]</span> <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			Help<span class="token punctuation">[</span>CurNum<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>solve<span class="token punctuation">[</span>LenOne<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		<span class="token keyword">else</span>
		<span class="token punctuation">{</span>
			Help<span class="token punctuation">[</span>CurNum<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>solve<span class="token punctuation">[</span>LenTwo<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">while</span><span class="token punctuation">(</span> LenOne<span class="token operator">&gt;=</span>Left <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		Help<span class="token punctuation">[</span>CurNum<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>solve<span class="token punctuation">[</span>LenOne<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">while</span><span class="token punctuation">(</span> LenTwo<span class="token operator">&gt;</span>mid <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		Help<span class="token punctuation">[</span>CurNum<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>solve<span class="token punctuation">[</span>LenTwo<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token function">copy</span><span class="token punctuation">(</span> Help<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> Help<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> solve<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">+</span>Left <span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> <span class="token function">MergeSort</span><span class="token punctuation">(</span><span class="token keyword">int</span> Left<span class="token punctuation">,</span> <span class="token keyword">int</span> Right<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> mid<span class="token operator">=</span>Left<span class="token operator">+</span><span class="token punctuation">(</span>Right<span class="token operator">-</span>Left<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
		<span class="token comment">//int mid=(Left+Right)/2;</span>
		<span class="token function">MergeSort</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">MergeSort</span><span class="token punctuation">(</span> mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//『注意事项』</span>
		<span class="token function">Merge</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br></div></div><h4 id="开拓思维的子函数1"><a href="#开拓思维的子函数1" class="header-anchor">#</a> 开拓思维的子函数1</h4> <p><a href="https://leetcode-cn.com/problems/merge-sorted-array/" target="_blank" rel="noopener noreferrer">88. 合并两个有序数组<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p> <ul><li>技巧——倒着来</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">void</span> <span class="token function">merge</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums1<span class="token punctuation">,</span> <span class="token keyword">int</span> m<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums2<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        
        <span class="token keyword">int</span> one<span class="token operator">=</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> two<span class="token operator">=</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> tag<span class="token operator">=</span>m<span class="token operator">+</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> one<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> two<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> nums1<span class="token punctuation">[</span>one<span class="token punctuation">]</span><span class="token operator">&gt;</span>nums2<span class="token punctuation">[</span>two<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                nums1<span class="token punctuation">[</span>tag<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>nums1<span class="token punctuation">[</span>one<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
                nums1<span class="token punctuation">[</span>tag<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>nums2<span class="token punctuation">[</span>two<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span> one<span class="token operator">&lt;</span><span class="token number">0</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> two<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> tag<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                nums1<span class="token punctuation">[</span>tag<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>nums2<span class="token punctuation">[</span>two<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span> two<span class="token operator">&lt;</span><span class="token number">0</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> one<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> tag<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                nums1<span class="token punctuation">[</span>tag<span class="token operator">--</span><span class="token punctuation">]</span><span class="token operator">=</span>nums1<span class="token punctuation">[</span>one<span class="token operator">--</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> <span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br></div></div><h3 id="_2-7-快速排序"><a href="#_2-7-快速排序" class="header-anchor">#</a> 2.7.快速排序</h3> <h4 id="_2-7-1-一般版本"><a href="#_2-7-1-一般版本" class="header-anchor">#</a> 2.7.1.一般版本</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">int</span> <span class="token function">Divide</span><span class="token punctuation">(</span> <span class="token keyword">int</span> start<span class="token punctuation">,</span> <span class="token keyword">int</span> end <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//假装，选最左边的元素作为坑</span>
	<span class="token keyword">int</span> SelectElement<span class="token operator">=</span>arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token punctuation">;</span>
    
	<span class="token keyword">while</span><span class="token punctuation">(</span> start<span class="token operator">&lt;</span>end <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">while</span><span class="token punctuation">(</span> start<span class="token operator">&lt;</span>end <span class="token operator">&amp;&amp;</span> arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token operator">&gt;</span>pos <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token operator">--</span>end<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token punctuation">;</span>
        
        <span class="token comment">//『『坑点』』2：arr[start]&lt;=pos取的是&lt;=</span>
		<span class="token keyword">while</span><span class="token punctuation">(</span> start<span class="token operator">&lt;</span>end <span class="token operator">&amp;&amp;</span> arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token operator">&lt;=</span>pos <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token operator">++</span>start<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token punctuation">;</span>
        
	<span class="token punctuation">}</span>

	<span class="token comment">//一定要记得把坑，填好</span>
	arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token operator">=</span>SelectElement<span class="token punctuation">;</span>

	<span class="token keyword">return</span> end<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">//注意，是『闭区间』</span>
<span class="token keyword">void</span> <span class="token function">QuickSort</span><span class="token punctuation">(</span> <span class="token keyword">int</span> Left<span class="token punctuation">,</span> <span class="token keyword">int</span> Right <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> PosHole<span class="token operator">=</span><span class="token function">Divide</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">QuickSort</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> PosHole<span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">QuickSort</span><span class="token punctuation">(</span> PosHole<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br></div></div><h4 id="_2-7-2-合并上面代码版本"><a href="#_2-7-2-合并上面代码版本" class="header-anchor">#</a> 2.7.2.合并上面代码版本</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">QuickSort</span><span class="token punctuation">(</span> <span class="token keyword">int</span> Left<span class="token punctuation">,</span> <span class="token keyword">int</span> Right <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token comment">//模拟参数传递</span>
		<span class="token keyword">int</span> start<span class="token operator">=</span>Left<span class="token punctuation">;</span>
		<span class="token keyword">int</span> end<span class="token operator">=</span>Right<span class="token punctuation">;</span>

		<span class="token keyword">int</span> pos<span class="token operator">=</span>arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token keyword">while</span><span class="token punctuation">(</span> start<span class="token operator">&lt;</span>end <span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">while</span><span class="token punctuation">(</span> start<span class="token operator">&lt;</span>end <span class="token operator">&amp;&amp;</span> arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token operator">&gt;</span>pos <span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				<span class="token operator">--</span>end<span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
			arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token punctuation">;</span>
			<span class="token keyword">while</span><span class="token punctuation">(</span> start<span class="token operator">&lt;</span>end <span class="token operator">&amp;&amp;</span> arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token operator">&lt;=</span>pos <span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				<span class="token operator">++</span>start<span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
			arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>

		<span class="token comment">//一定要记得把坑，填好</span>
		arr<span class="token punctuation">[</span>end<span class="token punctuation">]</span><span class="token operator">=</span>pos<span class="token punctuation">;</span>
		<span class="token keyword">int</span> PosHole<span class="token operator">=</span>start<span class="token punctuation">;</span>

		<span class="token function">QuickSort</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> PosHole<span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">QuickSort</span><span class="token punctuation">(</span> PosHole<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br></div></div><div class="language-txt line-numbers-mode"><pre class="language-text"><code>1、作为**最常用**的算法之一，最好能在一分钟内写出来，生活、工作、**面试**必备良品。
2、思路：其实选择一个数字枢轴作为枢纽pivot，左右指针向中间靠拢，将大于pivot的都置换到其右面，小于pivot的都置换到其左边。然后左递归，右递归，类似二叉树的先序遍历。
3、注意：下面的程序选择最左的数作为pivot，当然还可以随机选，选择哪个数也是比较有研究的，请查阅相关资料。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><h2 id="_03-排序『链表』模板⭐️"><a href="#_03-排序『链表』模板⭐️" class="header-anchor">#</a> 03.排序『链表』模板⭐️</h2> <h3 id="_3-1-选择排序"><a href="#_3-1-选择排序" class="header-anchor">#</a> 3.1.选择排序</h3> <ul><li><p><a href="https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=190&&tqId=35599&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking" target="_blank" rel="noopener noreferrer">牛客网-单链表的排序<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li> <li><p>LeetCode上<a href="https://leetcode-cn.com/problems/sort-list/submissions/" target="_blank" rel="noopener noreferrer">排序链表<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li></ul> <h4 id="_3-1-1不断链之狸猫换太子版『修改节点』"><a href="#_3-1-1不断链之狸猫换太子版『修改节点』" class="header-anchor">#</a> 3.1.1不断链之狸猫换太子版『修改节点』</h4> <ul><li>牛客和LeetCode上都会超时，但思路OK</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */</span>

<span class="token keyword">void</span> <span class="token function">swap</span><span class="token punctuation">(</span> ListNode <span class="token operator">*</span> a<span class="token punctuation">,</span> ListNode <span class="token operator">*</span> b<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> temp<span class="token operator">=</span>a<span class="token operator">-&gt;</span>val<span class="token punctuation">;</span>
    a<span class="token operator">-&gt;</span>val<span class="token operator">=</span>b<span class="token operator">-&gt;</span>val<span class="token punctuation">;</span>
    b<span class="token operator">-&gt;</span>val<span class="token operator">=</span>temp<span class="token punctuation">;</span>
    
    <span class="token comment">//a-&gt;val^=b-&gt;val;  //由于『优先级』，这样写是错误的，要写成 (a-&gt;val)^=(b-&gt;val)这样的</span>
    <span class="token comment">//b-&gt;val^=a-&gt;val;</span>
    <span class="token comment">//a-&gt;val^=b-&gt;val;</span>
<span class="token punctuation">}</span>

<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token comment">/**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */</span>
    ListNode<span class="token operator">*</span> <span class="token function">sortInList</span><span class="token punctuation">(</span>ListNode<span class="token operator">*</span> head<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// write code here</span>
        
        
        <span class="token comment">//****************************************************************************</span>
        ListNode <span class="token operator">*</span> cur<span class="token operator">=</span>head<span class="token punctuation">;</span>
        
        <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>cur <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            ListNode <span class="token operator">*</span> mintemp<span class="token operator">=</span>cur<span class="token punctuation">;</span>
            ListNode <span class="token operator">*</span> inner<span class="token operator">=</span>cur<span class="token punctuation">;</span>
            
            <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>inner <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span> inner<span class="token operator">-&gt;</span>val <span class="token operator">&lt;</span> mintemp<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    mintemp<span class="token operator">=</span>inner<span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                
                inner<span class="token operator">=</span>inner<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span><span class="token comment">//for inner loop</span>
            <span class="token punctuation">}</span>
            <span class="token function">swap</span><span class="token punctuation">(</span> mintemp<span class="token punctuation">,</span> cur <span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//简化代码</span>
            
            cur<span class="token operator">=</span>cur<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span><span class="token comment">//for outside loop</span>
        <span class="token punctuation">}</span>
        <span class="token comment">//****************************************************************************</span>
        
        <span class="token keyword">return</span> head<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br></div></div><h4 id="_3-1-2-断链写法『不修改节点』"><a href="#_3-1-2-断链写法『不修改节点』" class="header-anchor">#</a> 3.1.2.断链写法『不修改节点』</h4> <h3 id="_3-3-插入排序"><a href="#_3-3-插入排序" class="header-anchor">#</a> 3.3.插入排序</h3> <ul><li><p>LeetCode<a href="https://leetcode-cn.com/problems/insertion-sort-list/" target="_blank" rel="noopener noreferrer">147. 对链表进行插入排序<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li> <li><p>断链的写法</p></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    ListNode<span class="token operator">*</span> <span class="token function">insertionSortList</span><span class="token punctuation">(</span>ListNode<span class="token operator">*</span> head<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>head <span class="token operator">||</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>head<span class="token operator">-&gt;</span>next <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> head<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        ListNode <span class="token operator">*</span> sentry<span class="token operator">=</span><span class="token keyword">new</span> <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//表示</span>
        ListNode <span class="token operator">*</span> cur<span class="token operator">=</span>head<span class="token punctuation">;</span>                  <span class="token comment">//表示，要排序的一串节点中最开始的节点</span>
        <span class="token comment">//第1个大于等于Cur的节点</span>
        ListNode <span class="token operator">*</span> FirstGTECur<span class="token operator">=</span>sentry<span class="token punctuation">;</span>            <span class="token comment">//前面的节点中，排序完成的最后一个节点</span>
       

        <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>cur <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//找到一个比当前节点还大的节点，方便插入</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>FirstGTECur<span class="token operator">-&gt;</span>next <span class="token operator">&amp;&amp;</span> FirstGTECur<span class="token operator">-&gt;</span>next<span class="token operator">-&gt;</span>val <span class="token operator">&lt;</span> cur<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                FirstGTECur<span class="token operator">=</span>FirstGTECur<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//链表的拆解和链接</span>
            ListNode <span class="token operator">*</span> CurTempNext<span class="token operator">=</span>cur<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
            cur<span class="token operator">-&gt;</span>next<span class="token operator">=</span>FirstGTECur<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>    <span class="token comment">//链表的</span>
            FirstGTECur<span class="token operator">-&gt;</span>next<span class="token operator">=</span>cur<span class="token punctuation">;</span>

            FirstGTECur<span class="token operator">=</span>sentry<span class="token punctuation">;</span><span class="token comment">//重新回到原点，重新开始下一轮『核心』</span>
            cur<span class="token operator">=</span>CurTempNext<span class="token punctuation">;</span>   
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> sentry<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br></div></div><ul><li>参考自：<a href="https://leetcode-cn.com/problems/insertion-sort-list/solution/147-kao-cha-lian-biao-zong-he-cao-zuo-xiang-jie-by/" target="_blank" rel="noopener noreferrer">代码随想录<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h3 id="✅『2大』"><a href="#✅『2大』" class="header-anchor">#</a> ✅『2大』</h3> <h3 id="_3-6-归并排序"><a href="#_3-6-归并排序" class="header-anchor">#</a> 3.6.归并排序</h3> <h4 id="_1、子函数1"><a href="#_1、子函数1" class="header-anchor">#</a> 1、子函数1</h4> <ul><li><a href="https://leetcode-cn.com/problems/merge-two-sorted-lists/" target="_blank" rel="noopener noreferrer">21. 合并两个有序链表<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    ListNode<span class="token operator">*</span> <span class="token function">mergeTwoLists</span><span class="token punctuation">(</span>ListNode<span class="token operator">*</span> l1<span class="token punctuation">,</span> ListNode<span class="token operator">*</span> l2<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token operator">==</span>l1<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> l2<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token operator">==</span>l2<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> l1<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        ListNode <span class="token operator">*</span> rt<span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>l1<span class="token operator">-&gt;</span>val <span class="token operator">&lt;</span> l2<span class="token operator">-&gt;</span>val<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            rt<span class="token operator">=</span>l1<span class="token punctuation">;</span>
            l1<span class="token operator">=</span>l1<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            rt<span class="token operator">=</span>l2<span class="token punctuation">;</span>
            l2<span class="token operator">=</span>l2<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">//当前指针</span>
        ListNode <span class="token operator">*</span> p<span class="token operator">=</span>rt<span class="token punctuation">;</span>

        <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token operator">!=</span>l1 <span class="token operator">&amp;&amp;</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>l2<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>l1<span class="token operator">-&gt;</span>val <span class="token operator">&lt;</span> l2<span class="token operator">-&gt;</span>val<span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                p<span class="token operator">-&gt;</span>next<span class="token operator">=</span>l1<span class="token punctuation">;</span>
                p<span class="token operator">=</span>p<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>

                l1<span class="token operator">=</span>l1<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
                p<span class="token operator">-&gt;</span>next<span class="token operator">=</span>l2<span class="token punctuation">;</span>
                p<span class="token operator">=</span>p<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
                
                l2<span class="token operator">=</span>l2<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token operator">==</span>l1<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            p<span class="token operator">-&gt;</span>next<span class="token operator">=</span>l2<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            p<span class="token operator">-&gt;</span>next<span class="token operator">=</span>l1<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> rt<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br></div></div><ul><li>下面是这个的递归版本</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>ListNode<span class="token operator">*</span> <span class="token function">mergeTwoLists</span><span class="token punctuation">(</span>ListNode<span class="token operator">*</span> L1<span class="token punctuation">,</span> ListNode<span class="token operator">*</span> L2<span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>L1 <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> l2<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>L2 <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> L1<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    
    <span class="token comment">//递归</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> L1<span class="token operator">-&gt;</span>val <span class="token operator">&lt;</span> L2<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        L1<span class="token operator">-&gt;</span>next<span class="token operator">=</span><span class="token function">mergeTwoLists</span><span class="token punctuation">(</span> L1<span class="token operator">-&gt;</span>next<span class="token punctuation">,</span> L2 <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> L1<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">else</span>
    <span class="token punctuation">{</span>
        L2<span class="token operator">-&gt;</span>next<span class="token operator">=</span><span class="token function">mergeTwoLists</span><span class="token punctuation">(</span> L1 <span class="token punctuation">,</span> L2<span class="token operator">-&gt;</span>next <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> L2<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br></div></div><h3 id="_3-7-快速排序"><a href="#_3-7-快速排序" class="header-anchor">#</a> 3.7.快速排序</h3> <ul><li>LeetCode链表版：<a href="https://leetcode-cn.com/problems/sort-list/" target="_blank" rel="noopener noreferrer">148. 排序链表<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>下面是：不断链版本，使用『节点值交换』，狸猫换太子</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>
<span class="token keyword">void</span> <span class="token function">swap</span><span class="token punctuation">(</span> ListNode <span class="token operator">*</span> a<span class="token punctuation">,</span> ListNode <span class="token operator">*</span>b<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> temp<span class="token operator">=</span>a<span class="token operator">-&gt;</span>val<span class="token punctuation">;</span>
    a<span class="token operator">-&gt;</span>val<span class="token operator">=</span>b<span class="token operator">-&gt;</span>val<span class="token punctuation">;</span>
    b<span class="token operator">-&gt;</span>val<span class="token operator">=</span>temp<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

ListNode <span class="token operator">*</span> <span class="token function">Divide</span><span class="token punctuation">(</span> ListNode <span class="token operator">*</span> begin<span class="token punctuation">,</span> ListNode <span class="token operator">*</span> end <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token comment">//不需要排序的特例</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>begin <span class="token operator">||</span>begin<span class="token operator">==</span>end <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> begin<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">int</span> SelectKey<span class="token operator">=</span>begin<span class="token operator">-&gt;</span>val<span class="token punctuation">;</span>

    <span class="token comment">//左侧一大块比SelectKey小的元素，最右边的边界位置</span>
    <span class="token comment">//『此外，Left就是那个被挖出来的坑』</span>
    ListNode <span class="token operator">*</span> Left<span class="token operator">=</span>begin<span class="token punctuation">;</span>   
    ListNode <span class="token operator">*</span> Right<span class="token operator">=</span>begin<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span><span class="token comment">//右侧一大块&gt;=SelectKey的元素，最左边的边界位置</span>

    <span class="token comment">//想办法把&lt;Key的元素换到前面去</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span> Right<span class="token operator">!=</span>end <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> Right<span class="token operator">-&gt;</span>val <span class="token operator">&lt;</span> SelectKey <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//左侧让一个坑出来，准备和它换</span>
            Left<span class="token operator">=</span>Left<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
            <span class="token function">swap</span><span class="token punctuation">(</span>Left<span class="token punctuation">,</span>Right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        Right<span class="token operator">=</span>Right<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//把先前选择的SelectKey这个元素填进坑里面</span>
    <span class="token function">swap</span><span class="token punctuation">(</span>Left<span class="token punctuation">,</span>begin<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> Left<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">QuickSort</span><span class="token punctuation">(</span> ListNode <span class="token operator">*</span>  begin<span class="token punctuation">,</span> ListNode <span class="token operator">*</span> end <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token comment">//不需要排序的特例</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>begin  <span class="token operator">||</span> begin<span class="token operator">==</span>end  <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    ListNode <span class="token operator">*</span> pos<span class="token operator">=</span><span class="token function">Divide</span><span class="token punctuation">(</span> begin<span class="token punctuation">,</span> end <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">QuickSort</span><span class="token punctuation">(</span> begin<span class="token punctuation">,</span>pos <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">QuickSort</span><span class="token punctuation">(</span> pos<span class="token operator">-&gt;</span>next<span class="token punctuation">,</span>end <span class="token punctuation">)</span><span class="token punctuation">;</span> 
<span class="token punctuation">}</span>
<span class="token comment">/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    ListNode<span class="token operator">*</span> <span class="token function">sortList</span><span class="token punctuation">(</span>ListNode<span class="token operator">*</span> head<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">QuickSort</span><span class="token punctuation">(</span>head<span class="token punctuation">,</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> head<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br></div></div><h2 id="_04-三种线性排序"><a href="#_04-三种线性排序" class="header-anchor">#</a> 04.三种线性排序</h2> <h3 id="✅前述"><a href="#✅前述" class="header-anchor">#</a> ✅前述</h3> <p>《算法导论》中提到有定理表明：</p> <ul><li>任何比较排序在最坏的情况下都要经过O(nlogn)次比较</li></ul> <p>下面讨论三种<b>线性时间复杂度</b>的排序算法。</p> <ul><li>原因：这三种算法是用<b>运算</b>而不是<b>比较</b>来确定排序顺序的，所以能够突破这个定理的桎梏</li></ul> <p>排序算法4问：</p> <ul><li><p><b>1)时间复杂度</b></p></li> <li><p><b>2)空间复杂度</b></p></li> <li><p><b>3)排序是否原地</b></p> <ul><li><b>原地排序</b>：指不需要开辟额外空间</li></ul></li> <li><p><b>4)稳定性</b></p> <ul><li><b>稳定的排序</b>：具有相同值的元素在输出数组中的相对次序与他们在输入数组中的相对次序<b>相同</b></li> <li><b>意义</b>：只有当进行排序的数据还附带<b>&quot;卫星数据&quot;</b>时才比较重要。  eg.我们排序的是结构体的整数值，而整数值相同的，可能他的字符串不同。</li></ul></li></ul> <h3 id="✅计数排序（counting-sort）读音是第4声"><a href="#✅计数排序（counting-sort）读音是第4声" class="header-anchor">#</a> ✅计数排序（counting sort）读音是第4声</h3> <h3 id="_1-假设和操作"><a href="#_1-假设和操作" class="header-anchor">#</a> 1.假设和操作</h3> <blockquote><p>『<strong>输入数据假设</strong>』</p></blockquote> <p>假设n个输入元素中的每个元素都是在[min,max]区间的一个<b>整数</b>。
排序快的原因：</p> <ul><li><p>进行了上面的假设</p></li> <li><p>用空间换时间</p></li></ul> <blockquote><p>『<strong>操作</strong>』</p></blockquote> <blockquote><ul><li>1·建立一个长度为max-min+1的统计数组，元素初始化为0</li> <li>2·每次扫描进数据，那么对应的统计数组的值+1（数组每一个下标位置的值，代表了数列中对应整数出现的次数）<b>（计数一词的来源）</b></li> <li>3·遍历统计数组，输出数组元素的下标值，元素的值是几，就输出几次</li> <li>4·如果排序的带有<b>&quot;卫星数据&quot;</b>,则需要进行第4步————此举，保证了计数排序的稳定性</li></ul> <blockquote><ul><li>对已经填充完的统计数组，做一下变形——具体的请见下面场景</li> <li>根据情况，选择正向或者反向遍历统计数组</li></ul></blockquote></blockquote> <p>Tips：计数排序的稳定性很重要的另一个原因是：计数排序经常会被用作基数排序算法的一个子过程，为了使基数排序正确执行，计数排序必须是稳定的。</p> <p>创造场景如下：</p> <blockquote><ul><li>假设有一个企业的招聘系统规则如下</li></ul> <blockquote><ul><li>申请者需要投递简历，写好姓名，将得到一个原始的排名Ranking</li> <li>为了激励大家投递简历，发布了一条通知,我们的排名（Ranking）依据两个维度来给申请者面试名额</li></ul> <blockquote><ul><li>1.笔试成绩高者，排名（Ranking）高</li> <li>2.笔试成绩相同者，公司会给先投递简历的人高的排名（Ranking）<br>
此处体现了，排序的稳定性需求</li> <li>我们最后会将排名（Ranking）前4的申请者的名字（name）打印出来<br>
名字是我们要排序的成绩（grade）的卫星数据</li></ul></blockquote></blockquote></blockquote> <p>申请者的结构体设计如下</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">struct</span> <span class="token class-name">Apply</span>
<span class="token punctuation">{</span>
	<span class="token keyword">char</span> name<span class="token punctuation">[</span><span class="token number">20</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> grade<span class="token punctuation">;</span>
<span class="token punctuation">}</span>Ranking<span class="token punctuation">[</span><span class="token number">1000</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p>显然，我们的计数排序是根据结构体的元素，grade来排名。
此外，为了容易说明计数排序，我们假设，笔试成绩范围是0-10分
投递简历如下图：</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.1.png" alt="2020.5.30.1"></p> <ul><li>笔试完了，成绩如下图：</li></ul> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.2.png" alt="2020.5.30.2"></p> <p>请按照规则给上面排序，注意：小橙和小青的成绩都是6
操作：
1·建立一个长度为11的统计数组，元素初始化为0，表示我们的成绩为0-10
2·每次扫描进数据，那么对应的统计数组的值+1
显然获得统计数组如下图：</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.3.png" alt="2020.5.30.3"></p> <p>3.暂时，不需要输出
4.对统计数组进行变形：
方法，从倒数第2位开始，反向遍历统计数组，a[i]=a[i+1]+a[i];
相加的目的,是为了让统计数组存储的元素值,等于相应grade的排名的最终排序位置。</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.4.png" alt="2020.5.30.4"></p> <p>5.接下来,我们创建输出数组,长度和输入数组一致。
然后</p> <p><font style="background:yellow;">注意1）从后往前遍历</font></p> <p>原先的输入数组
小青，成绩6，查统计数组,值为2（有2个同成绩的），查变形后数组，放输出数组<b>第5位</b>
Tips：查到统计数组值为2，我们在放完小青到输出数组之后，需将变形后的数组的值减1，变成了4</p> <p><font style="background:yellow;">注意2）从5变成4,代表着下次再遇到6分的成绩时,最终排名是第4。（这就保证了计数排序的稳定性!）</font></p> <p>小蓝，成绩7,查统计数组,值为1（唯一），查变形后的数组，放输出数组的<b>第3位</b>
小绿，成绩5,查统计数组,值为1（唯一），查变形后的数组，放输出数组的<b>第6位</b>
小黄，成绩8,查统计数组,值为1（唯一），查变形后的数组，放输出数组的<b>第2位</b></p> <p>小橙，成绩6,查统计数组,值为2（有2个同成绩的），查变形后数组，知放输出数组<b>第4位</b>
我们在放完小橙到输出数组之后，需将变形后的数组的值，减1，变成了3</p> <p>小红,成绩9,查统计数组,值为1（唯一），查变形后的数组，知放输出数组的<b>第1位</b></p> <p>排序后结果（如图，保证了卫星数据的稳定性）：</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.5.png" alt="2020.5.30.5"></p> <h3 id="_2-算法分析"><a href="#_2-算法分析" class="header-anchor">#</a> 2.算法分析</h3> <ul><li><p>时间复杂度：O(n+m)其中m是原始数组的整数范围</p></li> <li><p>空间复杂度：O(n+m)</p></li> <li><p>是否原地排序：否</p></li> <li><p>稳定性：稳定</p></li> <li><p>数据结构：数组，hash</p></li></ul> <p>Tips：<font style="background:yellow;">有人也把统计数组的每个位置，叫做一个个桶，但我们暂时不这么叫，免得大家将桶排序和计数排序弄混了</font></p> <h3 id="_3-局限性"><a href="#_3-局限性" class="header-anchor">#</a> 3.局限性</h3> <blockquote><ul><li>1.当输入数组元素最大最小值差距过大时
比如给定20个随机整数,范围在0到1亿之间,这时若使用计数排序,需创建长度为1亿的数组。严重浪费空间,且时间复杂度也随之升高。
解决方案：见桶排序</li> <li>2.当输入数组元索不是整数，如字符，浮点数</li></ul> <blockquote><ul><li>如果数列中的元素都是小数,比如25.23 ,或是0.01这样子,无法创建对应的统计数组。
解决方案1：假如是0.3,0.13,0.001,0.22  我们可以将他们全乘1000，然后就转换为计数排序，输出的时候，记得除回来
解决方案2：见桶排序</li> <li>如果数列中的元素都是字符或字符串,比如abc,b,c
解决方案1：借助字符的ASCII码，按位赋权，转换hash为数字，再排序
解决方案2：见基数排序，借助字符的ASCII码。</li></ul></blockquote> <ul><li>4.如果，输入的元素是大整数，比如15位长的号码1234567894554541,可是,15位长的号码有多少种组合?这要建立一个大得不可想象的数组,才能装下所有可能出现的15位长的号码，很不划算!
解决方案：见基数排序（思想：减而治之）</li> <li>5.其他————碰到了再补充，总之，要灵活运用，而不是将某种算法运用场景当做教条，场景只是帮助更好的理解算法的一种方式。</li></ul></blockquote> <h3 id="✅基数排序（radix-sort）读音是第1声"><a href="#✅基数排序（radix-sort）读音是第1声" class="header-anchor">#</a> ✅基数排序（Radix sort）读音是第1声</h3> <h3 id="_1-操作"><a href="#_1-操作" class="header-anchor">#</a> 1.操作</h3> <p>需求：为如下一组英文单词排序</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.6.png" alt="2020.5.30.6"></p> <p>操作：我们把排序工作拆分成多个阶段,每一个阶段只根据一个字符(基数排序，基字的由来)进行计数排序, 一共排序k轮, k是元素长度。
如何将这些字符串按照字母顺序排序呢?
具体的
由于每个字符串的长度是3个字符,我们可以把排序工作拆分成3轮</p> <ul><li>第一轮:按照最低位字符排序。排序过程使用计数排序,把字母的ascii码对应到数组下标，第1轮排序结果如下:</li></ul> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.7.png" alt="2020.5.30.7"></p> <ul><li>第二轮:<b>在第一轮排序结果的基础上</b>,按照第二位字符排序，第2轮排序结果如下:</li></ul> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020.5.30.8.png" alt="2020.5.30.8"></p> <ul><li><font style="background:yellow;">
注意：这里使用的计数排序必须是稳定排序,这样才能保证第1轮排出的先后顺序在第2轮还能继续保持！</font></li> <li><font style="background:yellow;">
比如，在第1轮排序后,元素uue在元素yui之前。那么第二轮排序时,两者的第二位字符虽然同样是u,但先后顺序一定不能变,否则第1轮排序就白做了。</font></li> <li><p>第三轮：同理，略。</p> <ul><li>基数排序(Radix Sort)：形如这样把字符串元素按位拆分,每一个基位进行一次稳定性的排序的算法,就是基数排序</li> <li>基数排序既可以<b>从高位优先</b>进行排序（Most Significant Digit first ,简称MSD ）</li> <li>也可以<b>从低位优先</b>进行排序（Least Significant Digit first ,简称LSD）</li> <li>刚才我们所举的例子,就是典型的LSD方式的基数排序。</li></ul></li></ul> <h3 id="_2-疑问"><a href="#_2-疑问" class="header-anchor">#</a> 2.疑问</h3> <p>问：如果排序的字符串长度不规则呢?  比如有的字符串是5位，有的是3位</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>banana
apple
orange
ape
he
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p>毛主席说过，<strong>没有条件，我们就创造条件</strong>
创造条件：
我们以最长的字符串为准，其他长度不足的字符串，在<b>末尾补0</b>即可</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>banana
apple0
orange
ape000
he0000
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p>在排序时,我们把字符0当做是比a更小的字符,排序结果如下:</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>ape000
apple0
banana
he0000
orange
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><h3 id="_3-算法分析"><a href="#_3-算法分析" class="header-anchor">#</a> 3.算法分析</h3> <ul><li>时间复杂度：O(k(n+m))	其中m是原始数组的整数范围
由于字符串元素的长度k是一个固定常量，所以我们认为这个是一个线性的排序算法。</li> <li>空间复杂度：O(n+m)	至于空间复杂度，由于基数排序的辅助数组是反复重用的，所以基数排序的空间复杂度和计算排序一样。</li> <li>是否原地排序：否</li> <li>稳定性：稳定</li> <li>数据结构：数组，hash</li></ul> <font style="background:yellow;">
注意点：</font> <ul><li>1.上面的算法时间复杂度分析是不够完善的，其实上面的是以计数排序这种稳定排序作为基数排序的子过程的复杂度分析。基数排序，其实主要是强调，我们对待一些排序，可以按位（比如，我们二进制中，按照以2为基的任何位），来分别排序。</li> <li>2.推而广之：基数排序的子过程，可以是任何具有稳定性的排序算法（注意点）
<ul><li>eg.插入排序，折半插入排序，冒泡排序</li> <li>Tips:其实，基数排序的算法的时间复杂度分析依赖于我们所使用的稳定的排序算法！！！</li></ul></li></ul> <h3 id="✅桶排序（bucket-sort）"><a href="#✅桶排序（bucket-sort）" class="header-anchor">#</a> ✅桶排序（bucket sort）</h3> <h3 id="_1-假设和操作："><a href="#_1-假设和操作：" class="header-anchor">#</a> 1.假设和操作：</h3> <ul><li>碎碎念：桶排序同样是一种线性时间的排序算法。类似于计数排序所创建的<b>统计数组</b>，桶排序需要创建<b>若干个桶</b>来协助排序。这也大概是为什么有的人，将计数排序中的统计数组的叫做一个个桶的原因吧，然后推而广之，也在基数排序中叫桶
<ul><li><font style="background:yellow;">殊不知：有时就是这样的叫法把初学者弄混了，不知道，是不是有桶的都叫桶排序？</font></li> <li>其实，《算法导论》一书中，并没有把计数排序和基数排序中的统计数组叫桶...</li></ul></li></ul> <p>但是，其实桶排序体现的是一种思想，我们不用纠结的是&quot;桶&quot;到底是什么，我们需要的是根据实际情况去选择合适的数据结构去存储，实现这个抽象的&quot;桶&quot;，所以，我们也将计数和基数排序中的统计数组算做是&quot;桶&quot;点一种实现方式吧。</p> <p>与计数排序相似，因为对输入数据进行了某种假设，桶排序的速度也很快。
假设：输入数据服从<strong>均匀分布</strong></p> <p>那么,桶排序当中所谓的&quot;桶”，又是什么概念呢?
每一个桶(bucket)代表一个区间范围,里面可以承载一个或多个元素。</p> <ul><li>操作：
<ul><li>第一步，就是创建这些桶,确定每一个桶的区间范围</li> <li>第二步，将创建这些桶,分别都进行排序处理（由于，数据满足均匀分布，所以，我们的每个桶放的元素应该都差不多一样多，也就是均匀）</li> <li>第三步，合并桶，进行输出</li></ul></li></ul> <h3 id="_2-算法分析-2"><a href="#_2-算法分析-2" class="header-anchor">#</a> 2.算法分析</h3> <p>假设原始数列有n个元素,分成m个桶, 平均每个桶的元素个数为n/m。
下面我们来逐步分析算法复杂度:</p> <ul><li>第一步，求数列最大最小值,运算量为n。</li> <li>第二步，创建空桶,运算量为m。</li> <li>第三步，遍历原始数列,运算量为n。</li> <li>第四步，在每个桶内部做排序,若是使用了$0(nlogn)$的排序算法,所以运算量为
<code>$n/m * log(n/m)* m$</code></li> <li>第五步,输出排序数列,运算量为n。
加起来,总的运算为<code>$3n+m+ n/m * log(n/m)* m = 3n+m+ n(logn-logm)$</code>
去掉系数,时间复杂度为:
O(n+m+n(logn-logm) )</li></ul> <p>空间复杂度:
空桶占用的空间+数列在桶中占用的空间=O(n+m)</p> <ul><li>时间复杂度：O(n+m+n(logn-logm))</li> <li>空间复杂度：O(n+m)</li> <li>是否原地排序：否</li> <li>稳定性：若是桶内使用不稳定的排序，则不稳定，但是桶与桶之间是稳定的</li> <li>数据结构：数组，链表，堆...看场景</li></ul> <p>Tips：分析</p> <ul><li><p>时间复杂度：</p> <ul><li>最坏n方（一个桶)）</li> <li>最好为n（n个桶而且值排列均匀）</li></ul></li> <li><p>空间复杂度：</p> <ul><li>其实，要是想要空间复杂度最好，得用链表，但是那样时间复杂度就做不到最好</li></ul></li></ul> <h3 id="✅联系和总结"><a href="#✅联系和总结" class="header-anchor">#</a> ✅联系和总结</h3> <p>总的来说，计数排序，基数排序，桶排序都是用的空间换取时间的思想。
另外，我们的<strong>计数排序</strong>和<strong>基数排序</strong>都可以看做是<strong>桶排序</strong>，&quot;桶思想&quot;的一种特例。</p> <ul><li><p>由于，桶排序的复杂度分析很依赖于具体的数据，我们常用的反而是计数排序和基数排序。</p></li> <li><p>从桶排序的算法分析中，我们需要知道的是，没有绝对高效的算法，只有合适的算法应用场景！</p></li> <li><p>总的说来，算法的设计，一般体现的是用时间换空间，或者空间换时间。</p></li></ul> <h2 id="_05-查找类算法"><a href="#_05-查找类算法" class="header-anchor">#</a> 05.查找类算法</h2> <h3 id="_5-1-二分查找"><a href="#_5-1-二分查找" class="header-anchor">#</a> 5.1.二分查找</h3> <ul><li><a href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/" target="_blank" rel="noopener noreferrer">34. 在排序数组中查找元素的第一个和最后一个位置<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h4 id="_5-1-1-自建轮子"><a href="#_5-1-1-自建轮子" class="header-anchor">#</a> 5.1.1.自建轮子</h4> <h4 id="_5-1-2-stl解法"><a href="#_5-1-2-stl解法" class="header-anchor">#</a> 5.1.2.STL解法</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">searchRange</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">,</span> <span class="token keyword">int</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        pair<span class="token operator">&lt;</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator<span class="token punctuation">,</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator<span class="token operator">&gt;</span> solve<span class="token punctuation">;</span>
        solve<span class="token operator">=</span><span class="token function">equal_range</span><span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>nums<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>target<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">int</span> tag<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">:</span> nums<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> target<span class="token operator">==</span>i <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                tag<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ret<span class="token punctuation">;</span>
        
        <span class="token comment">//那显然后面就更加没有了</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">==</span>solve<span class="token punctuation">.</span>first  <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">1</span><span class="token operator">==</span>tag <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> solve<span class="token punctuation">.</span>first<span class="token operator">-</span>nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> solve<span class="token punctuation">.</span>second<span class="token operator">-</span>nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br></div></div><h3 id="_5-2-其他查找算法"><a href="#_5-2-其他查找算法" class="header-anchor">#</a> 5.2.其他查找算法</h3> <ul><li><a href="https://www.cnblogs.com/maybe2030/p/4715035.html" target="_blank" rel="noopener noreferrer">七大查找算法<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h2 id="参考资料"><a href="#参考资料" class="header-anchor">#</a> 参考资料</h2> <ul><li><a href="https://www.cnblogs.com/onepixel/p/7674659.html" target="_blank" rel="noopener noreferrer">十大排序算法模板<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/64.6f8bb1fa.js" defer></script>
  </body>
</html>
